/*
 * Copyright (c) 1997, 2013, Oracle and/or its affiliates. All rights reserved.
 * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 */

package java.util;

import java.util.function.Consumer;
import java.util.function.Predicate;
import java.util.function.UnaryOperator;

/**
 * <p>List接口的可变大小-数组的实现。
 * 实现了所有的可选列表操作，允许所有的元素，包括null。
 * 除了实现了List接口，这个类提供了一些方法，来操纵列表中内部存储的数组的大小。
 * （这个类大致与Vector相同，除了他没有被同步）
 * 
 * <p>size、isEmpty、get、set、iterator和listIterator操作在常量时间内运行。
 * add操作在平摊的常量时间内允许，增加n个元素，需要O(n)的实际。
 * 所有其他的现在在线性的时间内完成（大致上）
 * 与LinkedList实现相比，常量因素要低。
 * 
 * <p>每个ArrayList实例都有一个容量。
 * 容量是列表中存放元素的数组的大小。它永远最小与列表的大小一样大。
 * 当元素被添加到ArrayList中，它的容量自动增长。
 * 除了添加一个元素，消耗平摊的常量时间外，没有对增长策略的指定细节。
 * 
 * <p>应用程序可以增加ArrayList实例的容量，
 * 在使用ensureCapacity增加一大堆元素之前。
 * 这可以减少递增的重新分配的数量。
 * 
 * <p>注意：这个实现是不同步的。
 * 如果多线程并发地访问一个ArrayList实例，
 * 并且至少一个线程结构上修改了这个列表，那么它必须在外面同步。
 * （结构上的改变是增加，删除一个或多个元素，
 * 或者显式地改变依赖数组的大小，仅仅改变元素的值不会是一个结构上的改变）
 * 这通常是对封装列表的对象进行同步，来完成。
 * 如果没有这样的对象，列表应该使用Collections.synchronizedList来包装它。
 * 它通常该在创建时做，来防止意外对列表的非同步访问。
 * <pre>
 *   List list = Collections.synchronizedList(new ArrayList(...));</pre>
 * 
 * <p>返回的Iterator和ListIterator是快速失败的。
 * 如果Iterator创建后，列表在任何时间被结构上改变了，
 * 除了迭代器自己的remove和add方法外，迭代器会抛出ConcurrentModificationException。
 * 因此，面对并发的改变，Iterator快速失败，十分干净，
 * 而不是在将来某个不确定的时间，冒着风险，做任意的，不确定性的操作。
 *
 * <p>注意：不能保证Iterator的快速失败机制，
 * 因为，通常地说，在存在非同步的并发修改的情况下，不可能做出严格的保证。
 * 快速失败的迭代器基于最大努力抛出ConcurrentModificationException。
 * 因此，依赖于这个异常，写程序来保证正确性是错的，
 * 迭代器的快速失败机制，应该仅仅被用来探测bug
 *
 * @author  Josh Bloch
 * @author  Neal Gafter
 * @see     Collection
 * @see     List
 * @see     LinkedList
 * @see     Vector
 * @since   1.2 
 */

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    private static final long serialVersionUID = 8683452581122892189L;

    /**
     * 默认的初始容量，10
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * 共享的空数组实例，用于空的ArrayList实例。
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
     * 共享的空的数组实例，用于默认大小的空的数组实例。
     * 将它与EMPTY_ELEMENTDATA区别出来，来知道当第一个元素被加入时，膨胀多少。
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * 存储ArrayList的元素的数组缓冲。
     * ArrayList的容量是这个数组缓冲的长度。
     * 当加入第一个元素时，任何空的ArrayList，有着elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
     * 将被扩展到DEFAULT_CAPACITY。
     */
    transient Object[] elementData; // 非私有化，来简化嵌套类来访问（如sublist，Iterator）

    /**
     * ArrayList的大小（包含元素的数量），初始为0
     * @serial
     */
    private int size;

    /**
     * 使用指定的初始容量，创建一个空的列表。
     *
     * @param  initialCapacity  the initial capacity of the list
     * @throws IllegalArgumentException if the specified initial capacity
     *         is negative
     */
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
        	//如果>0，缓冲数组的大小为initialCapacity，
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
        	//如果等于0，为{}
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

    /**
     * 创建一个空的类别，初始容量为10（但是add之前为{}）
     */
    public ArrayList() {
    	//默认为为{}
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    /**
     * 创建一个包含指定集合元素的列表，顺序为集合迭代器返回的顺序。
     *
     * @param c the collection whose elements are to be placed into this list
     * @throws NullPointerException if the specified collection is null
     */
    public ArrayList(Collection<? extends E> c) {
    	//数组设定为c.toArray()，集合自己的变为数组的结果
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
        	//如果数组长度不为0
            // c.toArray 可能不返回（这是错误的）Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
            	//数组元素存入Ojbect数组中
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // 用空数组取代
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

    /**
     * 修剪ArrayList的容量，变为列表当前的大小。
     * 应用程序能使用这个操作，来最小化ArrayList实例的存储空间
     */
    public void trimToSize() {
        modCount++;
        if (size < elementData.length) {
        	//size < elementData.length，修剪
            elementData = (size == 0)
              ? EMPTY_ELEMENTDATA  //size==0 空数组
              : Arrays.copyOf(elementData, size);  //否则数组大小为size
        }
    }

    /**
     * 增加ArrayList实例的容量，如果需要，
     * 保证它能够持有数量最少为参数minCapacity指定的数量的元素。
     * 注意：这个方法没有被ArrayList内部方法使用，基本没人使用它
     *
     * @param   minCapacity   the desired minimum capacity
     */
    public void ensureCapacity(int minCapacity) {
        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            // any size if not default element table  如果不是默认的元素数组，为0
            ? 0
            // larger than default for default empty table. It's already
            // supposed to be at default size.
            : DEFAULT_CAPACITY;

        if (minCapacity > minExpand) {
        	//保证容量minCapacity
            ensureExplicitCapacity(minCapacity);
        }
    }

    /** 这个方法被各种add调用，还有readObject方法使用，这个操作增加modCount
     * 
     * @param minCapacity
     */
    private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        	//如果是空的默认数组,ArrayList()，大小为max(10,minCapacity),即至少为10，ensureExplicitCapacity(max(10,minCapacity))
        	//注意：如果调用ArrayList(0),数组为EMPTY_ELEMENTDATA，不进入这个if，直接ensureExplicitCapacity(minCapacity);
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        //保证容量minCapacity
        ensureExplicitCapacity(minCapacity);
    }

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // 如果minCapacity确实超出了数组长度，grow(minCapacity)
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

    /**
     * 数组分配的最大长度。
     * 一些虚拟机在数组中存放头字段。分配更大的数组可能导致OutOfMemoryError：要求的数组大小超过了虚拟器限制
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    /**
     * 增加容量，保证它能够持有数量最少为参数minCapacity指定的数量的元素。
     *
     * @param minCapacity the desired minimum capacity
     */
    private void grow(int minCapacity) {
        int oldCapacity = elementData.length;
        //新长度为1.5倍的旧容量
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
        	//如果新长度<minCapacity,新长度直接为minCapacity
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
        	//如果新长度大于MAX_ARRAY_SIZE，新长度为hugeCapacity(minCapacity)，为MAX_ARRAY_SIZE
        	//或Integer.MAX_VALUE（当minCapacity > MAX_ARRAY_SIZE）
            newCapacity = hugeCapacity(minCapacity);
        // 最小容量通常与大小接近，所以这是赚的：
        elementData = Arrays.copyOf(elementData, newCapacity);  //复制到大小为newCapacity的数组
    }

    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
        		//如果minCapacity > MAX_ARRAY_SIZE，返回Integer.MAX_VALUE，否则返回MAX_ARRAY_SIZE（即增加到MAX_ARRAY_SIZE）
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

    /**
     * 返回列表元素数量，直接返回size字段。
     *
     * @return the number of elements in this list
     */
    public int size() {
        return size;
    }

    /**
     * 根据size字段是否为0，返回列表是否为空
     *
     * @return <tt>true</tt> if this list contains no elements
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 如果集合包含指定元素，返回true。
     * 更正式地，当且仅当集合至少有一个这样的元素时，返回true。
     * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>.
     *
     * @param o element whose presence in this list is to be tested
     * @return <tt>true</tt> if this list contains the specified element
     */
    public boolean contains(Object o) {
    	//是否o的index>=0
        return indexOf(o) >= 0;
    }

    /**
     * 返回列表中第一次出现指定元素的位置，或者如果列表中不包含这个元素，返回-1。
     * 更正式地，返回最小的index i，
     * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
     * 或者如果没有这样的index，返回-1
     */
    public int indexOf(Object o) {
    	//直接根据下标，遍历elementData数组
        if (o == null) {
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

    /**
     * 返回列表中最后一次出现指定元素的位置，或者如果列表中不包含这个元素，返回-1。
     * 更正式地，返回最大的index i，
     * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
     * 或者如果没有这样的index，返回-1
     */
    public int lastIndexOf(Object o) {
        if (o == null) {
            for (int i = size-1; i >= 0; i--)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = size-1; i >= 0; i--)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

    /**
     * 返回ArrayList实例的一个浅复制（元素自身不被复制）
     *
     * @return a clone of this <tt>ArrayList</tt> instance
     */
    public Object clone() {
        try {
            ArrayList<?> v = (ArrayList<?>) super.clone();
            //将元素的引用复制过去，数组大小为size，而不是当前的容量
            v.elementData = Arrays.copyOf(elementData, size);
            v.modCount = 0;
            return v;
        } catch (CloneNotSupportedException e) {
            // this shouldn't happen, since we are Cloneable
            throw new InternalError(e);
        }
    }

    /**
     * 返回一个包含这个列表所有元素的数组。（从第一个到最后一个元素）
     *
     * <p>返回的数组是安全的，因为列表没有维持对它的引用
     * （换言而之，这个方法必须分配一个新的数组，即使列表内部已经有一个数组了）。
     * 因此调用者修改返回的数组是安全的。
     *
     * <p>这个方法是基于数组和基于列表的API之间的桥梁。
     *
     * @return an array containing all of the elements in this list in
     *         proper sequence
     */
    public Object[] toArray() {
    	//数组为elementData
    	//大小为size
        return Arrays.copyOf(elementData, size);
    }

    /**
     * <p>返回一个包含这个列表所有元素的数组。（从第一个到最后一个元素）
     * 返回的数组的运行时类型是指定数组的类型。
     * 如果列表适合这个指定的数组的大小，她就在里面返回。
     * 否则，创建一个新数组，类型为指定数组的运行时类型，大小为这个列表的大小。
     * 
     * <p>如果该列表适应指定的数组，有着剩余的空间（数组比列表有更多的元素），
     * 数组中的元素在列表的末尾的，被设置为null。
     * （如果调用者知道列表确实没有任何null元素，这才有助于决定列表的长度）
     *     
     *
     * @param a the array into which the elements of the list are to
     *          be stored, if it is big enough; otherwise, a new array of the
     *          same runtime type is allocated for this purpose.
     * @return an array containing the elements of the list
     * @throws ArrayStoreException if the runtime type of the specified array
     *         is not a supertype of the runtime type of every element in
     *         this list
     * @throws NullPointerException if the specified array is null
     */
    @SuppressWarnings("unchecked")
    public <T> T[] toArray(T[] a) {
        if (a.length < size)
            // 如果size比a.length大，返回一个a.getClass()类型的新数组，内容为elementData，大小为size
            return (T[]) Arrays.copyOf(elementData, size, a.getClass());
        //否则，复制在a的[0,size)处复制元素，后面的size处设置为null，之后的不管
        System.arraycopy(elementData, 0, a, 0, size);
        if (a.length > size)
            a[size] = null;
        return a;
    }

    // 基于位置的操作

    @SuppressWarnings("unchecked")
    E elementData(int index) {
    	//返回数组中index位置的元素，强转为E
        return (E) elementData[index];
    }

    /**
     * 返回列表中指定位置的元素。
     * index范围[0,size()-1]
     *
     * @param  index index of the element to return
     * @return the element at the specified position in this list
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E get(int index) {
        rangeCheck(index);
        //先检查范围，再在数组中根据下标，直接获取元素
        return elementData(index);
    }

    /**
     * 用指定元素替代列表中指定位置的元素，返回旧元素
     *
     * @param index index of the element to replace
     * @param element element to be stored at the specified position
     * @return the element previously at the specified position
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E set(int index, E element) {
        rangeCheck(index);
        //得到旧元素，设置新元素，返回旧元素
        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }

    /**
     * 在列表的最后加入一个指定元素
     *
     * @param e element to be appended to this list
     * @return <tt>true</tt> (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
    	//保证大小size=1，这个方法增加modCount
        ensureCapacityInternal(size + 1);  // Increments modCount!! 
        //size处为e，然后size++
        elementData[size++] = e;
        return true;
    }

    /**
     * 插入指定元素到列表的指定位置。elementData[index] = element。
     * 在这个位置的元素（如果有）和任何后边的元素被移动到右边（将它们的index+1）
     *
     * @param index index at which the specified element is to be inserted
     * @param element element to be inserted
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public void add(int index, E element) {
        rangeCheckForAdd(index);  //检查范围[0,size]

        ensureCapacityInternal(size + 1);  // 保证size+1的容量，modCount++
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);//index和随后size-index个，放到index+1去
        elementData[index] = element;  //index处为指定元素
        size++;
    }

    /**
     * 删除列表中指定位置的元素
     * 移动后面的元素到左边（index-1）。
     * 返回被移除的元素。
     *
     * @param index the index of the element to be removed
     * @return the element that was removed from the list
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E remove(int index) {
        rangeCheck(index);

        modCount++;
        E oldValue = elementData(index);  //指定位置的旧元素

        int numMoved = size - index - 1;  //需要被移动的元素的数量
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);  //index+1和随后size-index-1个，放到index去
        elementData[--size] = null; // 将size--位，设置为null，清理多出来的空间

        return oldValue;  // 返回被移除的元素
    }

    /**
     * 如果指定元素存在，从列表中移除指定元素。如果列表不包含这个元素，列表不变。
     * 更正式地说，移除一个index最小的这样的元素（如果这样的元素存在） ，
     * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>
     * 如果列表包含指定元素，返回true。（如果列表因为调用而改变，返回true）
     * 被移除的元素，可以认为被调用了remove(int)
     *
     * @param o element to be removed from this list, if present
     * @return <tt>true</tt> if this list contained the specified element
     */
    public boolean remove(Object o) {
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {
            for (int index = 0; index < size; index++)
            	//从前往后找
                if (o.equals(elementData[index])) {
                	//可以视为快速的remove(int)
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }

    /*
     * 私有的remove方法,被remove(Object)使用，跳过边界检查，不返回移除的元素，其余的和remove(int)一样
     */
    private void fastRemove(int index) {
        modCount++;
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work
    }

    /**
     * 移除列表中所有的元素。这个方法返回后，列表为空。
     */
    public void clear() {
        modCount++;

        // clear to let GC do its work
        for (int i = 0; i < size; i++)
        	//数组内部元素的引用，全部设置为null
            elementData[i] = null;
        //size设置为0
        size = 0;
    }

    /**
     * 将指定列表的所有元素加入到这个列表的最后，顺序为指定列表的迭代器的返回顺序。
     * 当执行操作时，如果修改指定列表，操作的结果未知。
     * （这意味着，如果如果指定列表是这个列表，而且列表是非空的，调用的结果未知）
     *
     * @param c collection containing elements to be added to this list
     * @return <tt>true</tt> if this list changed as a result of the call
     * @throws NullPointerException if the specified collection is null
     */
    public boolean addAll(Collection<? extends E> c) {
        Object[] a = c.toArray(); // c.toArray 根据c的Iterator的顺序，返回的数组
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // 保证数量size+a.length   Increments modCount
        System.arraycopy(a, 0, elementData, size, numNew); // 将a的从0开始，numNew个，放到数组的size处
        size += numNew; //size增加numNew个
        return numNew != 0;
    }

    /**
     * 将指定列表的所有元素加入到这个列表的指定位置。
     * 在这个位置的元素（如果有）和任何这个元素右边的元素，被移动到右边（增加它们的index）
     * 新的元素出现的顺序为指定列表的迭代器的返回顺序。
     *
     * @param index index at which to insert the first element from the
     *              specified collection
     * @param c collection containing elements to be added to this list
     * @return <tt>true</tt> if this list changed as a result of the call
     * @throws IndexOutOfBoundsException {@inheritDoc}
     * @throws NullPointerException if the specified collection is null
     */
    public boolean addAll(int index, Collection<? extends E> c) {
        rangeCheckForAdd(index);

        Object[] a = c.toArray();
        int numNew = a.length;  // 被加入的数量
        ensureCapacityInternal(size + numNew);  // Increments modCount

        int numMoved = size - index; // 被移动的数量
        if (numMoved > 0)
            System.arraycopy(elementData, index, elementData, index + numNew,
                             numMoved);  //先将数组的index处，numMoved个，放到index+numNew处

        System.arraycopy(a, 0, elementData, index, numNew);  // 将a的0处，numNew个，放到数组的index处
        size += numNew;
        return numNew != 0;
    }

    /**
     * 移除这个列表中所有index在fromIndex（包含）到toIndex（不包含）的元素。
     * 将后继的元素移到左边（减去index）。
     * 这种调用减少了列表toIndex - fromIndex个元素。
     * 如果toIndex==fromIndex，操作啥都不干。
     *
     * <p>这个方法被ArrayList的sublist的removeRange引用

     * @throws IndexOutOfBoundsException if {@code fromIndex} or
     *         {@code toIndex} is out of range
     *         ({@code fromIndex < 0 ||
     *          fromIndex >= size() ||
     *          toIndex > size() ||
     *          toIndex < fromIndex})
     */
    protected void removeRange(int fromIndex, int toIndex) {
        modCount++;
        int numMoved = size - toIndex;
        System.arraycopy(elementData, toIndex, elementData, fromIndex,
                         numMoved); //数组的toIndex，numMoved个，移动到数组的fromIndex

        // clear to let GC do its work
        int newSize = size - (toIndex-fromIndex);
        for (int i = newSize; i < size; i++) {
            elementData[i] = null; //后面的设置为null
        }
        size = newSize;
    }

    /**
     * 检查给定的index是否在范围内。给get，remove，set使用
     * 如果不，抛出适当的运行时异常。
     * 方法不检查index是否为负数：方法总是在任何数组访问前被使用，如果数组为负，会抛出ArrayIndexOutOfBoundsException.
     * <p>检查范围(-无穷,size)
     */
    private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    /**
     * 对add和addAll使用的rangeCheck版本。检查范围[0,size]
     */
    private void rangeCheckForAdd(int index) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    /**
     * 创建一个IndexOutOfBoundsException的详细信息。
     * 在错误处理代码的许多可能重构中，这种“大纲”在服务器和客户机vm上都表现得最好。
     * 
     */
    private String outOfBoundsMsg(int index) {
        return "Index: "+index+", Size: "+size;
    }

    /**
     * 删除这个列表中，所有已经包含在指定列表的元素
     *
     * @param c collection containing elements to be removed from this list
     * @return {@code true} if this list changed as a result of the call
     * @throws ClassCastException if the class of an element of this list
     *         is incompatible with the specified collection
     * (<a href="Collection.html#optional-restrictions">optional</a>)
     * @throws NullPointerException if this list contains a null element and the
     *         specified collection does not permit null elements
     * (<a href="Collection.html#optional-restrictions">optional</a>),
     *         or if the specified collection is null
     * @see Collection#contains(Object)
     */
    public boolean removeAll(Collection<?> c) {
        Objects.requireNonNull(c);
        return batchRemove(c, false);
    }

    /**
     * 列表中只保留指定列表包含的元素。
     * 换言而之，列表中移除所有不被指定列表包含的元素。
     *
     * @param c collection containing elements to be retained in this list
     * @return {@code true} if this list changed as a result of the call
     * @throws ClassCastException if the class of an element of this list
     *         is incompatible with the specified collection
     * (<a href="Collection.html#optional-restrictions">optional</a>)
     * @throws NullPointerException if this list contains a null element and the
     *         specified collection does not permit null elements
     * (<a href="Collection.html#optional-restrictions">optional</a>),
     *         or if the specified collection is null
     * @see Collection#contains(Object)
     */
    public boolean retainAll(Collection<?> c) {
        Objects.requireNonNull(c);
        return batchRemove(c, true);
    }

    /** 根据c.contains(elementData[r])，批量删除elementData的元素。
     *  使用双指针算法，直接覆盖，而不是一个个删除
     * @param c
     * @param complement
     * @return
     */
    private boolean batchRemove(Collection<?> c, boolean complement) {
        final Object[] elementData = this.elementData;
        int r = 0, w = 0;  //r和w是数组中读取，写入的指针，双指针算法
        boolean modified = false;
        try {
            for (; r < size; r++) //读取指针，不断递增到size
                if (c.contains(elementData[r]) == complement)
                	//remove，complement为false，即集合不包含r对应的元素，依次写入（即包含时，就不写入数组了）
                	//retain，为true，包含时写入，不包含时，不写入
                	//写入后，w++
                    elementData[w++] = elementData[r];
        } finally {
            // 保持AbstractCollection的兼容性
            // 如果c.contains() 抛出异常，此时r不为size
            if (r != size) {
                System.arraycopy(elementData, r,
                                 elementData, w,
                                 size - r); // 将数组的r开始，size-r个（即未被读取的），复制到w
                w += size - r;
            }
            if (w != size) {
                // clear to let GC do its work
                for (int i = w; i < size; i++)
                	//将w之后的，设置为null
                    elementData[i] = null;
                modCount += size - w;
                size = w;
                modified = true;
            }
        }
        return modified;
    }

    /**
     * 保存ArrayList实例的状态，到一个流。（序列化）
     *
     * @serialData The length of the array backing the <tt>ArrayList</tt>
     *             instance is emitted (int), followed by all of its elements
     *             (each an <tt>Object</tt>) in the proper order.
     */
    private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException{
        // 写出元素计数和任何隐藏的东西
        int expectedModCount = modCount;
        s.defaultWriteObject();

        // 输出size，作为容量，为了与clone方法兼容
        s.writeInt(size);

        // 以适当的顺序输出所有元素
        for (int i=0; i<size; i++) {
            s.writeObject(elementData[i]); // 一个个写出
        }

        if (modCount != expectedModCount) { //写完后比较modCount
            throw new ConcurrentModificationException();
        }
    }

    /**
     * 从流中，重组一个ArrayList实例（反序列化）
     */
    private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        elementData = EMPTY_ELEMENTDATA;

        // 读入大小和任何隐藏的东西
        s.defaultReadObject();

        // 读入容量，忽略
        s.readInt(); // ignored

        if (size > 0) {
            // 像clone方法，基于大小而不是容量分配数组
            ensureCapacityInternal(size); // 保证容量size

            Object[] a = elementData;
            // 以适当的顺序读入所有元素
            for (int i=0; i<size; i++) {
                a[i] = s.readObject(); // 一个个读入
            }
        }
    }

    /**
     * 返回一个覆盖列表中元素的ListIterator（以适当的顺序），
     * 以列表中指定位置开始。
     * 指定位置的元素是第一次调用ListIterator的next方法返回的元素。
     * 第一次调用ListIterator的previous方法返回的元素是指定index-1对应的元素。
     *
     * <p>The returned list iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
     *
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public ListIterator<E> listIterator(int index) {
        if (index < 0 || index > size)
            throw new IndexOutOfBoundsException("Index: "+index);
        return new ListItr(index);
    }

    /**
     * 返回一个覆盖列表中元素的ListIterator（以适当的顺序）
     *
     * <p>The returned list iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
     *
     * @see #listIterator(int)
     */
    public ListIterator<E> listIterator() {
        return new ListItr(0);
    }

    /**
     * 返回一个覆盖列表中元素的Iterator（以适当的顺序）
     *
     * <p>The returned iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
     *
     * @return an iterator over the elements in this list in proper sequence
     */
    public Iterator<E> iterator() {
        return new Itr();
    }

    /**
     * AbstractList.Itr 的优化版本
     */
    private class Itr implements Iterator<E> {
        int cursor;       // 下一个返回元素的index，初始为0
        int lastRet = -1; // 上一次返回元素的index，如果没有，为-1
        int expectedModCount = modCount;

        public boolean hasNext() {
            return cursor != size;
        }

        @SuppressWarnings("unchecked")
        public E next() {
            checkForComodification();
            int i = cursor;
            //检查cursor是否超出size和length
            if (i >= size)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i + 1;
            //返回elementData[cursor]，设置lastRet = cursor，cursor++，
            return (E) elementData[lastRet = i];
        }

        public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
            	//调用ArrayList.remove(lastRet)
                ArrayList.this.remove(lastRet);
                //cursor倒退为lastRet，lasetRet重设为-1，重设expectedModCount
                cursor = lastRet;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        @Override
        @SuppressWarnings("unchecked")
        public void forEachRemaining(Consumer<? super E> consumer) {
        	//重写forEachRemaining
            Objects.requireNonNull(consumer);
            final int size = ArrayList.this.size;
            int i = cursor;
            if (i >= size) {
                return;
            }
            final Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length) {
                throw new ConcurrentModificationException();
            }
            while (i != size && modCount == expectedModCount) {
            	//i范围[cursor,size)
                consumer.accept((E) elementData[i++]);
            }
            // 在while循环后，更新，减少堆的写入流量
            //如果正常结束，i=size，cursor=size，lastRet=size-1，modCount == expectedModCount
            //非正常结束，i就不为size，modCount != expectedModCount，后面会报错
            cursor = i;
            lastRet = i - 1;
            checkForComodification();
        }

        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }

    /**
     * AbstractList.ListItr的优化版本
     */
    private class ListItr extends Itr implements ListIterator<E> {
        ListItr(int index) {
            super();
            cursor = index; //设置cursor
        }

        public boolean hasPrevious() {
            return cursor != 0;
        }

        public int nextIndex() {
            return cursor;
        }

        public int previousIndex() {
            return cursor - 1;
        }

        @SuppressWarnings("unchecked")
        public E previous() {
            checkForComodification();
            int i = cursor - 1;
            if (i < 0)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i;
            // 返回cursor-1，cursor--，lastRet=cursor-1
            return (E) elementData[lastRet = i];
        }

        public void set(E e) {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
            	//在lastRet处set
                ArrayList.this.set(lastRet, e);
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        public void add(E e) {
            checkForComodification();

            try {
                int i = cursor;
                //add(cursor,e)
                ArrayList.this.add(i, e);
                //cursor++，重设lastRet
                //从而 下次next的元素不变，previous的是新的元素 e
                cursor = i + 1;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }
    }

    /**
     * <p>返回list一部分的视图，从指定的fromIndex（包含）到toIndex（不包含）。
     * （如果fromIndex和toIndex相等，返回的list为空）
     * 返回的列表有该列表支持，所以返回的列表的非结构性的改变会反映在这个列表中，反之亦然。
     * 返回的列表支持所有由这个列表支持的可选list操作。
     *
     * <p>这个方法不需要显示的范围操作（数组中常见的那种）。
     * 任何需要列表用作范围操作的操作，都可以传入一个subList视图，而不是一整个列表。
     * 例如：从列表中删除一个范围的元素：
     * 
     * <pre>{@code
     *      list.subList(from, to).clear();
     * }</pre>
     * 
     *
     * <p>可以用indexOf和lastIndexOf来构造类似的习语，
     * 所有Collections的语法能适用于一个subList
     * 
     * <p>如果支持的列表被结构性的改变了，而不是通过返回的列表改变，返回的列表的语义未知。
     * （结构性的改变是改变这个列表的大小或者以一种正则进行的迭代的方式扰乱列表）
     *
     * @throws IndexOutOfBoundsException {@inheritDoc}
     * @throws IllegalArgumentException {@inheritDoc}
     */
    public List<E> subList(int fromIndex, int toIndex) {
        subListRangeCheck(fromIndex, toIndex, size);
        return new SubList(this, 0, fromIndex, toIndex);
    }

    /** 0 <= fromIndex <= toIndex <= size
     * @param fromIndex
     * @param toIndex
     * @param size
     */
    static void subListRangeCheck(int fromIndex, int toIndex, int size) {
        if (fromIndex < 0)
            throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
        if (toIndex > size)
            throw new IndexOutOfBoundsException("toIndex = " + toIndex);
        if (fromIndex > toIndex)
            throw new IllegalArgumentException("fromIndex(" + fromIndex +
                                               ") > toIndex(" + toIndex + ")");
    }

    private class SubList extends AbstractList<E> implements RandomAccess {
        private final AbstractList<E> parent;
        // 在父亲list（ArrayList或sublist）的偏移量
        // add,remove的位置是parentOffset + index，这个是调用parent的add和remove方法
        // 可以发现sublist套sublist时，也是如abstractlist的sublist，一层套一层
        // 调用上一层的sublist的add方法，直到最上层ArrayList时，真正调用
        // 重要：之所以要一层层调用，是因为涉及到结构的变化，要让一层层的sublist都知道变化，所以要一层层调用，而不是直接对数组操作
        private final int parentOffset;
        
        // 自身在内部类SubList的外部类ArrayList的数组的偏移量，offset处为sublist开始的地方
        // get,set的位置为offset+index，这个是直接对数组进行操作
        private final int offset;
        
        // size为to-from
        int size;
        
        // sublist的sublist
        // 最初  return new SubList(this, 0, fromIndex, toIndex);
        // 之后  return new SubList(this, offset, fromIndex2, toIndex2);
        // 等于  return new SubList(this, 0 + fromIndex, fromIndex2, toIndex2);
        // 之后  return new SubList(this, fromIndex + fromIndex2, fromIndex3, toIndex3);

        SubList(AbstractList<E> parent,
                int offset, int fromIndex, int toIndex) {
            this.parent = parent;
            this.parentOffset = fromIndex; 
            this.offset = offset + fromIndex; 
            this.size = toIndex - fromIndex; 
            this.modCount = ArrayList.this.modCount;
        }

        public E set(int index, E e) {
            rangeCheck(index);
            checkForComodification();
            E oldValue = ArrayList.this.elementData(offset + index);
            ArrayList.this.elementData[offset + index] = e;
            return oldValue;
        }

        public E get(int index) {
            rangeCheck(index);
            checkForComodification();
            return ArrayList.this.elementData(offset + index);
        }

        public int size() {
            checkForComodification();
            return this.size;
        }

        public void add(int index, E e) {
            rangeCheckForAdd(index);
            checkForComodification();
            parent.add(parentOffset + index, e);
            this.modCount = parent.modCount;
            this.size++;
        }

        public E remove(int index) {
            rangeCheck(index);
            checkForComodification();
            E result = parent.remove(parentOffset + index);
            this.modCount = parent.modCount;
            this.size--;
            return result;
        }

        protected void removeRange(int fromIndex, int toIndex) {
            checkForComodification();
            parent.removeRange(parentOffset + fromIndex,
                               parentOffset + toIndex);
            this.modCount = parent.modCount;
            this.size -= toIndex - fromIndex;
        }

        public boolean addAll(Collection<? extends E> c) {
            return addAll(this.size, c);
        }

        public boolean addAll(int index, Collection<? extends E> c) {
            rangeCheckForAdd(index);
            int cSize = c.size();
            if (cSize==0)
                return false;

            checkForComodification();
            parent.addAll(parentOffset + index, c);
            this.modCount = parent.modCount;
            this.size += cSize;
            return true;
        }

        public Iterator<E> iterator() {
            return listIterator();
        }

        public ListIterator<E> listIterator(final int index) {
            checkForComodification();
            rangeCheckForAdd(index);
            final int offset = this.offset;

            return new ListIterator<E>() {
            	// next和previous返回的元素是外部类数组的cursor+offset
            	// remove和add是调用外部subList的remove(lastRet)和add(cursor)方法
                int cursor = index;
                int lastRet = -1;
                int expectedModCount = ArrayList.this.modCount;

                public boolean hasNext() {
                    return cursor != SubList.this.size;
                }

                @SuppressWarnings("unchecked")
                public E next() {
                    checkForComodification();
                    int i = cursor;
                    if (i >= SubList.this.size)
                        throw new NoSuchElementException();
                    Object[] elementData = ArrayList.this.elementData;
                    if (offset + i >= elementData.length)
                        throw new ConcurrentModificationException();
                    cursor = i + 1;
                    return (E) elementData[offset + (lastRet = i)];
                }

                public boolean hasPrevious() {
                    return cursor != 0;
                }

                @SuppressWarnings("unchecked")
                public E previous() {
                    checkForComodification();
                    int i = cursor - 1;
                    if (i < 0)
                        throw new NoSuchElementException();
                    Object[] elementData = ArrayList.this.elementData;
                    if (offset + i >= elementData.length)
                        throw new ConcurrentModificationException();
                    cursor = i;
                    return (E) elementData[offset + (lastRet = i)];
                }

                @SuppressWarnings("unchecked")
                public void forEachRemaining(Consumer<? super E> consumer) {
                    Objects.requireNonNull(consumer);
                    final int size = SubList.this.size;
                    int i = cursor;
                    if (i >= size) {
                        return;
                    }
                    final Object[] elementData = ArrayList.this.elementData;
                    if (offset + i >= elementData.length) {
                        throw new ConcurrentModificationException();
                    }
                    while (i != size && modCount == expectedModCount) {
                        consumer.accept((E) elementData[offset + (i++)]);
                    }
                    // update once at end of iteration to reduce heap write traffic
                    lastRet = cursor = i;
                    checkForComodification();
                }

                public int nextIndex() {
                    return cursor;
                }

                public int previousIndex() {
                    return cursor - 1;
                }

                public void remove() {
                    if (lastRet < 0)
                        throw new IllegalStateException();
                    checkForComodification();

                    try {
                        SubList.this.remove(lastRet);
                        cursor = lastRet;
                        lastRet = -1;
                        expectedModCount = ArrayList.this.modCount;
                    } catch (IndexOutOfBoundsException ex) {
                        throw new ConcurrentModificationException();
                    }
                }

                public void set(E e) {
                    if (lastRet < 0)
                        throw new IllegalStateException();
                    checkForComodification();

                    try {
                        ArrayList.this.set(offset + lastRet, e);
                    } catch (IndexOutOfBoundsException ex) {
                        throw new ConcurrentModificationException();
                    }
                }

                public void add(E e) {
                    checkForComodification();

                    try {
                        int i = cursor;
                        SubList.this.add(i, e);
                        cursor = i + 1;
                        lastRet = -1;
                        expectedModCount = ArrayList.this.modCount;
                    } catch (IndexOutOfBoundsException ex) {
                        throw new ConcurrentModificationException();
                    }
                }

                final void checkForComodification() {
                    if (expectedModCount != ArrayList.this.modCount)
                        throw new ConcurrentModificationException();
                }
            };
        }

        public List<E> subList(int fromIndex, int toIndex) {
            subListRangeCheck(fromIndex, toIndex, size);
            return new SubList(this, offset, fromIndex, toIndex);
        }

        private void rangeCheck(int index) {
            if (index < 0 || index >= this.size)
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }

        private void rangeCheckForAdd(int index) {
            if (index < 0 || index > this.size)
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }

        private String outOfBoundsMsg(int index) {
            return "Index: "+index+", Size: "+this.size;
        }

        private void checkForComodification() {
            if (ArrayList.this.modCount != this.modCount)
                throw new ConcurrentModificationException();
        }

        public Spliterator<E> spliterator() {
            checkForComodification();
            return new ArrayListSpliterator<E>(ArrayList.this, offset,
                                               offset + this.size, this.modCount);
        }
    }

    @Override
    public void forEach(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        final int expectedModCount = modCount;
        @SuppressWarnings("unchecked")
        final E[] elementData = (E[]) this.elementData;
        final int size = this.size;
        //不使用Iterator而是直接对数组元素进行遍历
        for (int i=0; modCount == expectedModCount && i < size; i++) {
            action.accept(elementData[i]);
        }
        //在所有元素遍历中，遍历前和遍历完，之间，如果出现modCount不一致，就报错
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
    }

    /**
     * 创建一个迟绑定和快速失败的spliterator，覆盖这个列表的元素
     *
     * <p>这个spliterator报告是SIZED，SUBSIZED，ORDERED。
     * 覆盖的实现应该报告额外的特征值。
     *
     * @return a {@code Spliterator} over the elements in this list
     * @since 1.8
     */
    @Override
    public Spliterator<E> spliterator() {
        return new ArrayListSpliterator<>(this, 0, -1, 0);
    }

    /** 基于index，一次分割成两个，懒初始化的spliterator*/
    static final class ArrayListSpliterator<E> implements Spliterator<E> {

        /*
         * 如果ArrayList是不可变的，或者结构不可变的（没有add，remove等待），
         * 我们能用Arrays.spliterator来实现他们的分割器。
         * 相反，我们再遍历过程中，检测出足够多的干扰，不牺牲太多的性能。
         * 我们主要依赖modCount。
         * 这些不能保证检测出太多的并发违背，并且有时对线程内的干扰过于保守，
         * 但在实践中能探测出足够的问题。
         * 为了实现这一点，
         * 1 我们懒初始化fence和expectedModCount，直到最迟的时刻，
         * 即我们需要提交我们正在检查的状态，直到提高精度。
         * （这不适用于SubList，那会创建非懒的spliterator）
         * 2 我们只在forEach的末尾进行ConcurrentModificationException检查
         * （性能最敏感的方法）
         * 当时用forEach（与迭代器相反），我们通常仅仅在action后，探测干扰，而不是在之前。
         * 进一步ConcurrentModificationException触发的检查适用于所有其他可能违反假设的情况，
         * 例如null或给定其size()的过小的elementData数组，这只可能由于干扰而发生。
         * 这允许forEach的内部循环可以在没有进一步检查的情况下运行，简化了lambda解析。
         * 虽然这确实需要很多检查，注意：在常见情况list.stream().forEach(a)，
         * 除了forEach内部，不会有其他地方进行检查或者计算。
         * 其他更少使用的方法不能利用大部分的流线型。
         * 
         */
    	//list就是外层的ArrayList，分割出去的spliterator也是外层的
        private final ArrayList<E> list;
        private int index; // 当前的index，在advance或split时改变
        private int fence; // -1 直到被使用; 之后是最后一个能到达的index+1 （size）
        private int expectedModCount; // 当fence设置时，初始化

        /** 创建一个新的spliterator，覆盖给定的范围   return new ArrayListSpliterator<>(this, 0, -1, 0);*/
        ArrayListSpliterator(ArrayList<E> list, int origin, int fence,
                             int expectedModCount) {
            this.list = list; // OK if null unless traversed
            this.index = origin;
            this.fence = fence;
            this.expectedModCount = expectedModCount;
        }

        private int getFence() { // 第一次使用时，初始化fence=size
            int hi; // (forEach 方法出现的专门的变量)
            ArrayList<E> lst;
            if ((hi = fence) < 0) { // 如果fence>=0，直接返回fence
                if ((lst = list) == null)
                    hi = fence = 0; // 如果list为null
                else {
                    expectedModCount = lst.modCount; //否则，此时设置modCount和size给expectedModCount，fence
                    hi = fence = lst.size;
                }
            }
            return hi;
        }

        public ArrayListSpliterator<E> trySplit() {
            int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
            return (lo >= mid) ? null : // 分割一半，除非太少了，只剩0-3个元素
            // 自身：[mid,fence) 给出去的：[index,mid)	
                new ArrayListSpliterator<E>(list, lo, index = mid,
                                            expectedModCount);
        }

        public boolean tryAdvance(Consumer<? super E> action) {
            if (action == null)
                throw new NullPointerException();
            int hi = getFence(), i = index;
            if (i < hi) { // 如果index<fence才执行，否则返回false
                index = i + 1; // index++
                @SuppressWarnings("unchecked") E e = (E)list.elementData[i]; //根据index得到list数组的元素
                action.accept(e); //对e执行操作
                if (list.modCount != expectedModCount)
                    throw new ConcurrentModificationException(); //操作完后，检验modcount
                return true;
            }
            return false;
        }

        public void forEachRemaining(Consumer<? super E> action) {
        	// i为index，hi为fence，mc为modCount
            int i, hi, mc; // hoist accesses and checks from loop
            ArrayList<E> lst; Object[] a;
            if (action == null)
                throw new NullPointerException();
            if ((lst = list) != null && (a = lst.elementData) != null) {// 如果list和里面的数组不为null
                if ((hi = fence) < 0) { // 如果fence没有被初始化
                    mc = lst.modCount; // 初始化modCount
                    hi = lst.size; // 初始化 hi
                }
                else
                    mc = expectedModCount;
                if ((i = index) >= 0 && (index = hi) <= a.length) { //设置index为fence
                    for (; i < hi; ++i) {
                    	//从index循环到fence
                        @SuppressWarnings("unchecked") E e = (E) a[i];
                        action.accept(e);
                    }
                    //循环结束后，检验modCount
                    if (lst.modCount == mc)
                        return;
                }
            }
            //  检验不通过，到这里，抛出异常
            throw new ConcurrentModificationException();
        }

        public long estimateSize() {
        	// 返回fence-index
            return (long) (getFence() - index);
        }

        public int characteristics() {
        	// ORDERED，SIZED，SUBSIZED
            return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
        }
    }

    @Override
    public boolean removeIf(Predicate<? super E> filter) {
        Objects.requireNonNull(filter);
        // 校验哪个元素会被移除
        // filter进行predicate时，抛出的任何异常，会让集合不被修改
        int removeCount = 0; // 被移除的元素个数
        final BitSet removeSet = new BitSet(size); // 哪位被set为true，哪位就被移除
        final int expectedModCount = modCount;
        final int size = this.size;
        for (int i=0; modCount == expectedModCount && i < size; i++) {
            @SuppressWarnings("unchecked")
            //i到size，进行循环
            final E element = (E) elementData[i];
            if (filter.test(element)) {
            	//如果返回true记录这个被移除的元素，和被移除的元素的个数
                removeSet.set(i);
                removeCount++;
            }
        }
        //如果在检验过程中，有modCount != expectedModCount ，抛出异常
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }

        // 将剩余元素向左移动，覆盖被移除的元素
        final boolean anyToRemove = removeCount > 0;
        if (anyToRemove) {
        	// 如果 removeCount>0 
            final int newSize = size - removeCount;
            for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
            	// i为读指针，j为写指针
            	// i为在指定的起始索引上或之后发生的第一个位的索引，该位的索引被设置为false。
            	// 即跳过设置为true的索引，即被删除的元素
                i = removeSet.nextClearBit(i);
                elementData[j] = elementData[i];
            }
            for (int k=newSize; k < size; k++) {
            	// 剩余的空间设置为null
                elementData[k] = null;  // Let gc do its work
            }
            this.size = newSize;
            if (modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }
            modCount++;
        }

        return anyToRemove;
    }

    @Override
    @SuppressWarnings("unchecked")
    public void replaceAll(UnaryOperator<E> operator) {
        Objects.requireNonNull(operator);
        final int expectedModCount = modCount;
        final int size = this.size;
        for (int i=0; modCount == expectedModCount && i < size; i++) {
        	//元素变为operator.apply的结果
            elementData[i] = operator.apply((E) elementData[i]);
        }
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
        modCount++;
    }

    @Override
    @SuppressWarnings("unchecked")
    public void sort(Comparator<? super E> c) {
        final int expectedModCount = modCount;
        //使用Arrays.sort直接排序数组，从0到size
        Arrays.sort((E[]) elementData, 0, size, c);
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
        modCount++;
    }
}
